A computer network may be viewed as a group of nodes connected by point-to-point communication channels. Each output channel of a node has a scheduler that selects packets to be transmitted through a channel associated with the scheduler.
Packets from different flows are stored in queues and the scheduler processes information associated with the head packet in each queue to determine which packet should be transmitted on the channel. The scheduler guarantees a minimum packet transmission rate to each queue where the sum of the guaranteed transmission rates must not be greater than the packet transmission rate of the channel. Thus, the packet transmission rate of the channel is much greater than the packet transmission rate guaranteed to any queue.
Packets are transmitted serially through the channel. When the channel is idle the scheduler selects a head packet from one of the queues, based on some priority scheme, and forwards it to the channel for transmission. Each queue has its packets transmitted as if it were the only source using a channel having a channel packet transmission rate equal to the guaranteed packet transmission rate of the queue.
Many schedulers utilize timestamps as the basis for scheduling packets to be transmitted. Time stamps may indicate the time at which a packet would finish transmitting if it were transmitted from the queue at the guaranteed packet transmission rate. For example, if a packet of length 5 reached the head of a queue at time 0, with the queue having a guaranteed packet transmission rate of 1, then the time stamp would be 5. In order for the channel to provide the guaranteed packet transmission rate it must complete transmitting the packet before a time value is equal to 5.
Schedulers may be implemented as binary search trees that have their leaf nodes populated by the time stamps of different head packets. A search of the nodes of the tree is required to determine which packet to schedule. Two-key search trees have also been used where the two keys are a start time and a finish time. For packets stored in a queue, the finish time of a preceding packet is the start time of a following packet.
Other data structures such as calendars can also be utilized as schedulers. A calendar has a series of time slots of a set precision for storing time stamps. For example, a calendar may have slots of width one second that would represent the sequence of times 1, 2, 3, . . . N. A time stamp equal to 1.5 would be stored in the “1” slot of the calendar.
Historically, the problem with calendars is lack of accuracy. In order to achieve the same kind of accuracy as a time stamp based scheduler, a calendar must have a large number of slots, each the size equivalent to the unit of time of the time stamp. For example, to match the accuracy of a 14-bit time stamp, the calendar needs 16K slots. This creates two problems. First, the number of time slots grows exponentially with accuracy (in number of equivalent time stamp bits), leading to impractical demand on storage associated with the calendar slots.
The other problem is that when the calendar slot is very granular the calendar can become sparsely populated. This leads to worst case O(N) operations to walk the calendar, where N is the number of slots. To deal with this problem, extra speedup mechanisms, such as a bit vector to represent slot occupancy, are often implemented in order to skip empty slots quickly.
Tree based schedulers generally search for an arbitrary key value, which requires serial access of the nodes and many operations. Calendar data structures generally require the size of memory to grow exponentially with accuracy, which limits their utility.
The challenges in the field of designing schedulers continue to increase with demands for more and better techniques having greater speed while reducing memory requirements. Therefore, a need has arisen for a new system and method for scheduling the transmission of packets.